/**
 * Copyright 厦门中软海晟信息技术有限公司 版权所有 违者必究 2019
 */
package com.leetCode;

import com.leetCode.structure.TreeNode;

/**
 * @author : sunzb(sunzb@hsit.com.cn)
 * @date: 2019/5/13
 */
public class _10_235_LowestCommonAncestorOfABinarySearchTree {

    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        while (root != null) {
            int parentVal = root.val;
            if (p.val > parentVal && q.val > parentVal)
                root = root.right;
            else if (p.val < parentVal && q.val < parentVal)
                root = root.left;
            else
                return root;
        }
        return null;
    }

    public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return root;
        if (p.val > root.val && q.val > root.val)
            return lowestCommonAncestor1(root.right, p, q);
        else if (p.val < root.val && q.val < root.val)
            return lowestCommonAncestor1(root.left, p, q);
        else
            return root;
    }

    public static void main(String[] args) {

    }
}
